package com.aqie.medium.tree;

import com.aqie.easy.structure.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 513 树左下角的值
 * todo
 */
public class FindBottomLeftValue {
    /**
     * DFS
     * @param root
     * @return
     */
    int level = -1, res = 0;
    public int findBottomLeftValue(TreeNode root) {
        helper(root, 0);
        return res;
    }

    private void helper(TreeNode root, int A) {
        if (root.left == null && root.right == null){
            if (A > level){
                level = A;
                res = root.val;
            }
            return;
        }
        if (root.left!=null) helper(root.left,A+1);    //先进左子树，这样在深度相同的条件下，返回左子树的结果
        if (root.right!=null) helper(root.right,A+1);
    }

    /**
     * 队列 BFS
     * @param root
     * @return
     */
    public int findBottomLeftValue2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>(){{
            add(root);
        }};
        TreeNode curNode = null;
        while (queue.size() > 0){
            curNode = queue.remove();
            if (curNode.right != null) queue.add(curNode.right);
            if (curNode.left != null) queue.add(curNode.left);
        }
        return curNode.val;
    }
}
